// 2025/4/4
// https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/?envType=daily-question&envId=2025-04-04
// 最深叶节点的最近公共祖先

class Solution {
    public:
        TreeNode* ans;
        int count, ansCount;
    
        int dfs(TreeNode* root)
        {
            if (root == nullptr) return 0;
    
            count++;
            int left = dfs(root->left);
            int right = dfs(root->right);
            count--;
    
            if (left == right && count + left >= ansCount)
            {
                ans = root;
                ansCount = count + left;
            }
    
            return max(left, right) + 1;
        }
    
        TreeNode* lcaDeepestLeaves(TreeNode* root) {
            ans = nullptr;
            count = ansCount = 0;
            dfs(root);
            return ans;
        }
    };